/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-11-26
 * Time: 23:25
 */
public class test2 {
    /*
    LeetCode 1314  矩阵前缀和
    给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
     */
    // 此题是关于一个二位前缀和的题目
    // 难点在于边界情况的处理
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m =mat.length;
        int n = mat[0].length;

        // 预处理前缀和
        int [][]dp = new int[m+1][n+1];
        for(int i =1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }

        // 使用前缀和
        int [][]ret = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int x1 = Math.max(0,i-k)+1;
                int y1 = Math.max(0,j-k)+1;
                int x2 = Math.min(m-1,i+k)+1;
                int y2 = Math.min(n-1,j+k)+1;
                ret[i][j] = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
            }
        }
        return ret;
    }
}
